package com.aqie.easy.binary;

/**
 * @Function: 868. 二进制间距 : 两个连续1间最大距离
 * @Author: aqie
 * @Date: 2019/7/1 20:14
 * todo
 */
public class BinaryGap {
    public static int binaryGap(int N) {
        //大顶堆，容量11
        // PriorityQueue<Integer> maxHeap = new PriorityQueue<>(11, (i1, i2) -> i2 - i1);
        int[] A = new int[32];
        int t = 0;
        for (int i = 0; i < 32; ++i)
            if (((N >> i) & 1) != 0)
                A[t++] = i;

        int ans = 0;
        for (int i = 0; i < t - 1; ++i)
            ans = Math.max(ans, A[i+1] - A[i]);
        return ans;


    }

    /**
     * 我们将存储 last，这是被添加到虚拟数组 A 中的最后一个值。如果 N 的第 i 位（此处应当有索引 last < i ）为 1，
     * 那么一个候选答案就是 i - last，然后新增到 A 的最后一个值被更新为 i，即 last = i。
     *
     * @param N
     * @return
     */
    public static int binaryGap2(int N) {
        int last = -1, ans = 0;
        for (int i = 0; i < 32; ++i)
            if (((N >> i) & 1) > 0) {
                if (last >= 0)
                    ans = Math.max(ans, i - last);
                last = i;
            }

        return ans;
    }

    public static void main(String[] args) {
        binaryGap(5);
    }
}
